Make your own free website on Tripod.com

Dynamic Memory Heaps for Quartus Forth

Copyright © 2000 Kristopher D. Johnson. All Rights Reserved.

Introduction

This is an implementation of dynamic memory allocation for Quartus Forth.

Quartus Forth provides implementations of the standard Forth words ALLOCATE, FREE, and RESIZE. However, there is a problem with the implementation of ALLOCATE. It uses the Palm OS memory allocation function to allocate a memory chunk, and then uses the >rel word to translate the 32-bit absolute address to a 16-bit relative address. The translation to a 16-bit relative address often fails on newer versions of the Palm OS, so ALLOCATE fails even when there is plenty of memory available.

One workaround is to repeatedly call ALLOCATE in a loop until it succeeds. However, I don't like the non-determinism of this approach, and there is no way to know whether it will continue to work with newer versions of the Palm OS. So, I've written my own dynamic heap allocation routines that use dictionary data space. This eliminates reliance upon the Palm OS memory allocation routines.

In addition to the standard words, this implementation provides a generic way to manage multiple heaps. So, you might want to put all your strings in one heap, I/O buffers in another, or whatever.

Source files

heapmem.txt definitions of ALLOCATE, FREE, and RESIZE. Needs heapchunks and heapconst.
heap.txt definitions of HEAP, HEAP-ALLOCATE, HEAP-FREE, and HEAP-RESIZE. Needs heapchunks and heapconst.
heapchunks.txt chunk management words used by heap
heapconst.txt constants used by other heap words

License

Copyright © 2000 Kristopher D. Johnson

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Limitations

8K Heap

The default size of the heap used by ALLOCATE, FREE, and RESIZE is eight kilobytes. If this is too small or too large for your application, you can change the constant definition in heapchunks.txt. There is no way to resize a heap after it has been created.

No Error Checking

This implementation never checks the validity of addresses or of the heap state. So if you FREE a chunk twice, or overwrite the end of the allocated area, results are undefined. If you're lucky, it will crash. If you're not lucky, you'll just get really weird behavior.

Fragmentation

The implementation does try to reuse freed chunks. However, it does not attempt to "merge" freed blocks. For example, say you start out with an 8K heap, you allocate two 2K chunks, and then free them. At this point, the heap will consist of two 2K freed chunks and a 4K chunk. If you then try to allocate 6K, it will fail.

I may add the block-merging capabilities some day, but in the meantime, use the following tips to avoid problems:


Author:

Kris Johnson
Last modified: Sun Oct 29 12:39:56 EST 2000